package rong;

public abstract class Tree<T extends Comparable<T>, N extends Node<T, N>> {
	N root;
	
	public abstract N add(T data);
	public abstract N delete(N x);
	
	public void rotateLeft(N x) {
		checkBelonging(x);
		N xp = x.parrent;
		N xr = x.right;
		if (xr == null) {
			return;
		}
		N xrl = xr.left;
		xr.parrent = xp;
		if (xp==null) 
			root = xr;
		if (xp!=null) {
			if (x==xp.left) 
				xp.left = xr;
			else 
				xp.right = xr;
		}
		x.parrent = xr;
		xr.left = x;
		if (xrl!=null){
			xrl.parrent = x;
		}
		x.right = xrl;
	}
	
	public void rotateRight(N x) {
		checkBelonging(x);
		N xp = x.parrent;
		N xl = x.left;
		if (xl == null) {
			return;
		}
		N xlr = xl.right;
		xl.parrent = xp;
		if (xp==null) 
			root = xl;
		if (xp!=null) {
			if (x==xp.left) 
				xp.left = xl;
			else 
				xp.right = xl;
		}
		x.parrent = xl;
		xl.right = x;
		if (xlr!=null){
			xlr.parrent = x;
		}
		x.left = xlr;
	}
	
	protected void checkBelonging(N x) {
		while (x.parrent!=null) {
			x = x.parrent;
		}
		if (x!=root) {
			throw new IllegalArgumentException(x + "is no in the tree " + root);
		}
	}
	
	public int getHeight() {
		if (root==null) {
			return 0;
		}
		return getHeight(root);
	}
	
	private int getHeight(N x) {
		if (x==null) {
			return 0;
		}
		return 1 + Math.max(getHeight(x.left), getHeight(x.right));
	}
}
